//KMP algorithm
//use it to find the son string

#include <bits/stdc++.h>
using namespace std;

int find(string ss, string s); //朴素算法
int kmpfind(string ss, string s); //kmp快速匹配算法

int main() 
{
	cout << "Input the bigger string: ";
	string ss, s;
	cin >> ss;
	cout << "Input the searcher string: ";
	cin >> s;
	cout << "The time is " << find(ss, s) << " (use usual way)" << endl;
	cout << "The time is " << kmpfind(ss, s) << " (use kmp way)(debug)" << endl;
	return 0;
}

int kmpfind(string ss, string s) //在这里实现KMP匹配算法 
{
	int i; //i就是每一次跳跃的步数
	for (i = 1; i < s.length(); i ++) {
		if (s[0] == s[i]) break;
	}

	//下面是正式的逻辑
	//确定下标数字
	return 1;
	
	
}

int find(string ss, string s)
{
	int tem = 0;
	int sig;
	for (int j = 0; j < ss.length(); j ++) {
		int sig = 1;
		for (int i = 0; i < s.length(); i ++) {
			if (ss[j + i] != s[i]) {
				sig = 0;
				break;
			}
		}
		if (sig == 1) {
			tem ++;
		}
	}
	return tem;
}
